package red.book._2._1;

/**
 * @Auther: wangbw
 * @Date:2020/3/15
 * @Description: red.book._2._1
 * @version: 1.0
 */
public class LogarithmSort {
    private static int[] myArr;

    public static void main(String[] args) {
        int[] arr = { 5, 3, 1, 4, 2 };
        LogarithmSort.sort1(arr);
        /*System.out.println(Arrays.toString(arr));
        arr = new int[]{5, 3, 1, 4, 2};
        SquareSort.sort2(arr);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{5, 3, 1, 4, 2};
        SquareSort.sort3(arr);
        System.out.println(Arrays.toString(arr));*/
    }

    /**
     * 归并排序
     * @param arr
     */
    private static void sort1(int[] arr) {
        myArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            myArr[i] = arr[i];
        }
        sort11(arr, 0 , arr.length - 1);
    }

    private static void sort11(int[] arr, int lo, int hi) {
        if(lo >= hi){
            return;
        }
        int mid = (lo + hi) / 2;
        sort11(arr, lo, mid);
        sort11(arr, mid, hi);
        merge(arr, lo, mid, hi);
    }

    private static void merge(int[] arr, int lo, int mid, int hi) {
        int j = mid + 1;
        int i = lo;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                arr[k] = myArr[j++];
            else if (j >= hi)
                arr[k] = myArr[i++];
            else if (myArr[i] < myArr[j])
                arr[k] = myArr[i++];
            else
                arr[k] = myArr[j++];
        }
    }
}

